# coding:utf-8

from typing import List


class Solution:
    # 有序部分可以直接二分查找
    def BinarySearch(self, nums: List[int], left: int, right: int, target: int) -> int:
        mid = (right-left) // 2
        if nums[left] < nums[mid]:
            # 左边有序
            pass
        else:
            # 右边有序
            pass


    # nums按升序排序且值互不相同
    def search(self, nums: List[int], target: int) -> int:
        # 二分查找,将数组分成两部分，一部分肯定是有序的，一部分肯定是无序的
        left = 0
        right = len(nums)-1
        while(left <= right):
            mid = (left+right)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < nums[right]:
                # 右边是有序的
                if nums[mid] < target and target <= nums[right]:
                    # 此时在右边
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                # 此时在左边有序
                if nums[left] <= target and target < nums[mid]:
                    right = right - 1
                else:
                    left = mid + 1

        return -1

if __name__ == '__main__':
    solu = Solution()
    # print(solu.strStr('a','a'))
    print(solu.search([1], 0))
